package io.adrainty.algorithm.leetcode.normal;

/**
 * @link <a href="https://leetcode.cn/problems/interleaving-string/">...</a>
 * @author adrainty
 * @version v1.0.0
 * @since 2024/5/2 22:58
 */
public class Solution97 {

    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), t = s3.length();
        if (m + n != t) return false;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i < m; i++) {
            if (s1.charAt(i) == s3.charAt(i) && dp[i][0]) dp[i + 1][0] = true;
        }
        for (int j = 0; j < n; j++) {
            if (s2.charAt(j) == s3.charAt(j) && dp[0][j]) dp[0][j + 1] = true;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s3.charAt(i + j - 1)) dp[i][j] = dp[i][j] || dp[i - 1][j];
                if (s2.charAt(j - 1) == s3.charAt(i + j - 1)) dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}
